Định nghĩa lớp độ phức tạp

Một lớp độ phức tạp là một tập hợp các vấn đề có độ phức tạp tương tự nhau. Các lớp độ phức tạp thường được định nghĩa theo các yếu tố sau:

• Thể loại vấn đề: thể loại phổ biến nhất là bài toán quyết định. Ngoài ra còn có bài toán hàm, bài toán đếm, bài toán tối ưu, bài toán có lời hứa, v.v.
• Mô hình tính toán: mô hình phổ biến nhất là máy Turing tất định. Ngoài ra còn có máy Turing bất định, mạch Boole, máy Turing lượng tử, mạch đơn điệu, v.v.
• Loại tài nguyên bị giới hạn và giới hạn cụ thể: chẳng hạn như "thời gian đa thức", "bộ nhớ lôgarit", v.v.

Các lớp độ phức tạp quan trọng

Quan hệ giữa các lớp độ phức tạp

Lớp độ phức tạp	Mô hình tính toán	Giới hạn tài nguyên
DTIME(f(n))	Máy Turing đơn định	Thời gian f(n)
P	Máy Turing đơn định	Thời gian poly(n)
EXPTIME	Máy Turing đơn định	Thời gian 2poly(n)
NTIME(f(n))	Máy Turing không đơn định	Thời gian f(n)
NP	Máy Turing không đơn định	Thời gian poly(n)
NEXPTIME	Máy Turing không đơn định	Thời gian 2poly(n)
DSPACE(f(n))	Máy Turing đơn định	Bộ nhớ f(n)
L	Máy Turing đơn định	Bộ nhớ O(log n)
PSPACE	Máy Turing đơn định	Bộ nhớ poly(n)
EXPSPACE	Máy Turing đơn định	Bộ nhớ 2poly(n)
NSPACE(f(n))	Máy Turing không đơn định	Bộ nhớ f(n)
NL	Máy Turing không đơn định	Bộ nhớ O(log n)
NPSPACE	Máy Turing không đơn định	Bộ nhớ poly(n)
NEXPSPACE	Máy Turing không đơn định	Bộ nhớ 2poly(n)

Theo định lý Savitch, PSPACE = NPSPACE và EXPSPACE = NEXPSPACE.

Một số lớp độ phức tạp quan trọng khác bao gồm BPP, ZPP, RP là các lớp định nghĩa trên máy Turing ngẫu nhiên, AC và NC là các lớp định nghĩa trên mạch logic Boole, và BQP và QMA là các lớp định nghĩa trên máy Turing lượng tử. #P là một lớp độ phức tạp quan trọng cho các bài toán đếm. Các lớp như IP và AM được định nghĩa thông qua hệ thống chứng minh tương tác. ALL là lớp tất cả các bài toán quyết định.

Các định lý cấp bậc

Với các lớp độ phức tạp định nghĩa như trên, một vấn đề đáng quan tâm là liệu với nhiều tài nguyên hơn, chẳng hạn như nhiều thời gian hơn, tập hợp các bài toán giải được có nhiều lên hay không. Cụ thể hơn, mặc dù DTIME(n) rõ ràng là tập hợp con của DTIME(n2), một câu hỏi lý thú là liệu mối quan hệ tập hợp con có chặt hay không. Với thời gian và bộ nhớ, câu hỏi trên được trả lời bởi các định lý cấp bậc thời gian và bộ nhớ. Cụ thể hơn, định lý cấp bậc thời gian là

DTIME ⁡ ( f ( n ) ) ⊊ DTIME ⁡ ( f ( n ) ⋅ log 2 ⁡ ( f ( n ) ) ) {\displaystyle \operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}} .

Định lý cấp bậc bộ nhớ là

DSPACE ⁡ ( f ( n ) ) ⊊ DSPACE ⁡ ( f ( n ) ⋅ log ⁡ ( f ( n ) ) ) {\displaystyle \operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}} .

Các định lý cấp bậc thời gian và bộ nhớ là cơ sở cho hầu hết các kết quả phân tách các lớp độ phức tạp. Ví dụ như định lý cấp bậc thời gian cho ta thấy P là tập hợp con chặt của EXPTIME, và định lý cấp bậc bộ nhớ cho ta thấy L là tập con chặt của PSPACE.

Quy về

Nhiều lớp độ phức tạp được định nghĩa thông qua khái niệm phép quy về. Một phép quy về là một biến đổi từ một bài toán này thành một bài toán khác. Nó thâu tóm khái niệm trực giác một bài toán ít nhất là khó bằng một bài toán khác. Nếu một bài toán X có thể được giải bằng thuật toán cho bài toán Y thì X không khó hơn Y, và ta nói X quy về Y. Có nhiều kiểu quy về khác nhau, tùy theo phương pháp quy về, chẳng hạn như phép quy về Cook, phép quy về Karp, phép quy về Levin, và tùy theo độ phức tạp của phép quy về, chẳng hạn như quy về trong thời gian đa thức, hoặc quy về trong bộ nhớ lôgarit.

Phép quy về phổ biến nhất là quy về trong thời gian đa thức. Điều này có nghĩa là thuật toán quy về chạy trong thời gian đa thức. Ví dụ như bài toán tính bình phương của một số nguyên có thể được quy về bài toán nhân hai số nguyên. Có nghĩa là thuật toán nhân hai số nguyên có thể dùng để tính bình phương một số bằng cách dùng số nguyên cần tính bình phương làm cả hai thừa số cho thuật toán nhân số. Do đó, tính bình phương không khó hơn phép nhân, bởi vì tính bình phương có thể quy về phép nhân.

Định nghĩa trên dẫn tới khái niệm khó cho một lớp độ phức tạp. Một bài toán X là khó cho lớp bài toán C nếu mọi bài toán trong C có thể quy về X. Khi đó, không có bài toán nào trong C là khó hơn X do một thuật toán cho X có thể giải bất kì bài toán nào trong C. Dĩ nhiên khái niệm bài toán khó tùy thuộc vào loại quy về được sử dụng. Cho các lớp độ phức tạp lớn hơn P, quy về trong thời gian đa thức thường được sử dụng. Ví dụ như tập hợp các bài toán khó cho NP là tập hợp các bài toán NP-khó.

Nếu bài toán X nằm trong C và là khó cho C, thì X là đầy đủ cho C. Điều này có nghĩa là X là bài toán khó nhất trong C. (Do có thể có nhiều bài toán cùng độ khó, có thể nói là X là một trong những bài toán khó nhất trong C). Do vậy, lớp NP-đầy đủ chứa những bài toán khó nhất trong NP, theo nghĩa chúng là những bài toán có nhiều khả năng nhất không giải được trong P. Do bài toán P = NP vẫn chưa được giải, nếu có thể quy một bài toán NP-đầy đủ, Π2 về bài toán Π1 thì chưa có thuật toán thời gian đa thức nào cho Π1. Bởi vì nếu có thuật toán thời gian đa thức cho Π1 thì cũng có thuật toán thời gian đa thức cho Π2. Tương tự như vậy, do mọi bài toán trong NP đều có thể quy về các bài toán NP-đầy đủ, nếu có thể giải được một bài toán NP-đầy đủ trong thời gian đa thức thì P = NP.[2]